package leetcode._06_回溯;

import org.junit.Test;

import java.util.*;

/**
 * @author pppppp
 * @date 2022/3/4 16:09
 * 给你一份航线列表 tickets ，其中 tickets[i] = [fromi, toi] 表示飞机出发和降落的机场地点。请你对该行程进行重新规划排序。
 *
 * 所有这些机票都属于一个从 JFK（肯尼迪国际机场）出发的先生，所以该行程必须从 JFK 开始。如果存在多种有效的行程，请你按字典排序返回最小的行程组合。
 *
 * 例如，行程 ["JFK", "LGA"] 与 ["JFK", "LGB"] 相比就更小，排序更靠前。
 * 假定所有机票至少存在一种合理的行程。且所有的机票 必须都用一次 且 只能用一次。
 *
 * * 示例 1：
 * 输入：tickets = [["MUC","LHR"],["JFK","MUC"],["SFO","SJC"],["LHR","SFO"]]
 * 输出：["JFK","MUC","LHR","SFO","SJC"]
 *
 * 示例 2：
 * 输入：tickets = [["JFK","SFO"],["JFK","ATL"],["SFO","ATL"],["ATL","JFK"],["ATL","SFO"]]
 * 输出：["JFK","ATL","JFK","SFO","ATL","SFO"]
 * 解释：另一种有效的行程是 ["JFK","SFO","ATL","JFK","ATL","SFO"] ，但是它字典排序更大更靠后。

 */
public class _332_重新安排行程 {

    @Test
    public void T_1(){
        String [][] src = {{"A","C"},{"C","A"},{"A","B"},{"B","A"},};
        List<List<String>> tickets = new ArrayList<>();
        for (String[] s : src) {
            ArrayList<String> t = new ArrayList<>();
            t.add(s[0]);
            t.add(s[1]);
            tickets.add(t);
        }
        List<String> itinerary2 = findItinerary2(tickets);
        System.out.println();
    }


    public List<String> findItinerary2(List<List<String>> tickets) {
        // 因为逆序插入，所以用链表
        List<String> ans = new LinkedList<>();
        if (tickets == null || tickets.size() == 0) {
            return ans;
        }
        Map<String, List<String>> graph = new HashMap<>();
        for (List<String> pair : tickets) {
            // 因为涉及删除操作，我们用链表
            List<String> nbr = graph.computeIfAbsent(pair.get(0), k -> new LinkedList<>());
            nbr.add(pair.get(1));
        }
        // 按目的顶点排序
        graph.values().forEach(x -> x.sort(String::compareTo));
        visit(graph, "A", ans);
        return ans;
    }
    // DFS方式遍历图，当走到不能走为止，再将节点加入到答案
    private void visit(Map<String, List<String>> graph, String src, List<String> ans) {
        List<String> nbr = graph.get(src);
        while (nbr != null && nbr.size() > 0) {
            String dest = nbr.remove(0);
            visit(graph, dest, ans);
        }
        ans.add(0, src); // 逆序插入
    }



    List<String> res = new ArrayList<>();

    public List<String> findItinerary(List<List<String>> tickets) {
        //from,             dest,    number
        Map<String, TreeMap<String, Integer>> map = new HashMap<>();
        for(List<String> ticket : tickets){
            String from = ticket.get(0);
            String to   = ticket.get(1);

            map.putIfAbsent(from, new TreeMap<>());
            TreeMap<String, Integer> treeMap = map.get(from);
            treeMap.put(to, treeMap.getOrDefault(to, 0) + 1);
        }

        res.add("JFK");
        backtrack(tickets, map, 0);

        return res;
    }

    private boolean backtrack(List<List<String>> tickets, Map<String, TreeMap<String, Integer>> map,int progress){
        if(progress == tickets.size()){
            return true;
        }

        TreeMap<String, Integer> tos = map.get(res.get(res.size() - 1));
        if(tos == null || tos.isEmpty() || tos.size() == 0) {
            return false;
        }

        for(String str : tos.keySet()){
            if(tos.get(str) == 0) {
                continue;
            }

            res.add(str);
            tos.put(str, tos.get(str) - 1);

            if(backtrack(tickets, map, progress + 1)) {
                return true;
            }

            res.remove(res.size() - 1);
            tos.put(str, tos.get(str) + 1);
        }

        return false;
    }
}
